//
//  main.c
//  Huffman
//
//  Created by zhuoooo on 2022/6/24.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//  https://www.cnblogs.com/wuyuankun/p/3982216.html

#include <stdio.h>
#define MAXBIT 100
#define MAXVALUE 10000   //节点最大值
#define MAXLEAF 30   //最大叶子节点数
#define MAXNODE MAXLEAF*2-1   //最优二叉树的总结点数=叶子节点数*2-1

typedef struct
{
    int bit[MAXBIT];
    int start;
}HCodeType;

typedef struct
{
    int weight;   //权值
    int parent;   //父母节点
    int lchild;   //左孩子
    int rchild;   //右孩子
    int value;    //节点处的值
}HNodeType;


HNodeType HuffNode[MAXNODE];//定义全局变量和数组可以自动初始化， 记录节点信息
HCodeType HuffCode[MAXLEAF], cd;

void HuffmanTree(HNodeType HuffNode[MAXNODE], int n);//构造包含这n个节点的Huffman树(最优二叉树)
void HuffmanCode(HCodeType HuffCode[MAXLEAF], HNodeType HuffNode[MAXNODE], HCodeType cd, int n);//构造Huffman编码


int main(int argc, const char * argv[]) {
    int n;
    printf("请输入叶子节点数n: ");
    scanf("%d", &n);
    printf("\n");
    HuffmanTree(HuffNode, n);
    HuffmanCode(HuffCode, HuffNode, cd, n);
    return 0;
}

//构造包含这n个节点的Huffman树(最优二叉树)
void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
{
    int i, j, m1, m2,x1, x2;
    //m1,m2构造哈夫曼树不同过程中两个最小权值结点的权值
    //x1,x2构造哈夫曼树不同过程种两个最小权值结点在数组中的序号
    
    for (i = 0; i < 2 * n - 1; i++)  //初始化存放哈夫曼数组的结点
    {
        HuffNode[i].weight = 0;
        HuffNode[i].parent = -1;
        HuffNode[i].lchild = -1;
        HuffNode[i].rchild = -1;
        HuffNode[i].value = i;
    }
    
    printf("请依次输入%d个叶子节点出现的频率:  \n", n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &HuffNode[i].weight);  //节点权重
    }
    printf("\n");
    
    for (i = 0; i < n - 1; i++)   //循环构造哈夫曼树，n个叶子结点需要n-1次构建
    {
        m1 = m2 = MAXVALUE;
        x1 = x2 = 0;
        for (j = 0; j < n + i; j++)//新建立的节点的下标是原来的叶子总结点数+i即n+i
        {
            if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)  //权值最小且没有父母节点
            {
                m2 = m1;
                x2 = x1;
                m1 = HuffNode[j].weight;   //最小权值赋给m1
                x1 = j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
            {
                m2 = HuffNode[j].weight;
                x2 = j;
            }
        }
        HuffNode[x1].parent = n + i;
        HuffNode[x2].parent = n + i;
        HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;  //父母节点的权值等于左右孩子节点之和
        HuffNode[n + i].lchild = x1;
        HuffNode[n + i].rchild = x2;
        printf("第%d次处理的两个叶子节点权值为:  %d, %d\n", i + 1, HuffNode[x1].weight, HuffNode[x2].weight);
        printf("\n");
    }
}

//构造Huffman编码
void HuffmanCode(HCodeType HuffCode[MAXLEAF], HNodeType HuffNode[MAXNODE], HCodeType cd, int n)
{
    int i, c, p, j;
    for (i = 0; i < n; i++)
    {
        cd.start = n - 1;  //n个叶子节点最多构建n-1次
        c = i;   //c记录当前叶子节点下标
        p = HuffNode[c].parent;   //记录当前节点的父母节点下标
        while (p != -1)  //没有父母节点
        {
            if (HuffNode[p].lchild == c)  //c为其父母节点的左孩子
            {
                cd.bit[cd.start] = 0;   //左节点编码为0
            }
            else
            {
                cd.bit[cd.start] = 1;   //右节点编码为1
            }
            cd.start--;   //自底而上编码
            c = p;      //将前一个的父母节点作为当前节点
            p = HuffNode[c].parent;
        }
        for (j = cd.start + 1; j < n; j++)
        {
            HuffCode[i].bit[j] = cd.bit[j];
        }
        HuffCode[i].start = cd.start;
    }
    for (i = 0; i < n; i++)
    {
        printf("第%d个叶子节点的Huffman编码为:  ", i+1);
        for (j = HuffCode[i].start + 1; j < n; j++)
        {
            printf("%d", HuffCode[i].bit[j]);
        }
        printf("  编码层序为(自底向上):%d", HuffCode[i].start);
        printf("\n");
    }
}
